package com.lw.leetcode.hash.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1600. 王位继承顺序
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/3 14:48
 */
public class ThroneInheritance {

    private String kingName;
    private Map<String, List<String>> map = new HashMap<>();
    private Set<String> deathSet = new HashSet<>();
    private int count = 1;

    public ThroneInheritance(String kingName) {
        this.kingName = kingName;
        map.put(kingName, new ArrayList<>());
    }

    public void birth(String parentName, String childName) {
        map.get(parentName).add(childName);
        map.put(childName, new ArrayList<>());
        count++;
    }

    public void death(String name) {
        deathSet.add(name);
        count--;
    }

    public List<String> getInheritanceOrder() {
        List<String> result = new ArrayList<>(count);
        dfs(result, kingName);
        return result;
    }

    private void dfs(List<String> result, String name) {
        if (!deathSet.contains(name)) {
            result.add(name);
        }
        for (String subName : map.get(name)) {
            dfs(result, subName);
        }
    }

}
